package model.parser;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.LinkedList;
import java.util.Stack;
import java.util.Queue;

import model.semantics.Node;

import model.tokens.*;

/**
 * 
 */

public class Parser<T> {
	private Lexer<T> myLexer;
	private List<Token<T>> tokens;

	/**
	 * Constructs a parser.
	 */
	public Parser(String tokenFile, String syntaxFile) {
		myLexer = new Lexer<T>(tokenFile, syntaxFile);
	}

	/**
	 * Parses an expression.
	 * @param expression a string expression to be parsed.
	 * @return the root node of the expression tree generated for the expression.
	 */
	public Node<T> parse(String expression) {
		tokens = myLexer.makeTokensFromExpressionString(expression);
		return processExpression();
		
	}

	/**
	 * Uses the Dijkstra shunting-yard algorithm to generate an RPN output from the input list
	 * of tokens, so that an abstract syntax tree can be generated.
	 * 
	 * @param tokens a list of tokens
	 * @return a stack of tokens representing the list of commands.
	 */
	public Node<T> processExpression() {
		Stack<Token<T>> operatorStack = new Stack<Token<T>>();
		Stack<Node<T>> output = new Stack<Node<T>>();
		
		Token<T> token;
		while(!tokens.isEmpty()) {
			token = tokens.remove(0);
			if(token instanceof RightGroupToken)
				break;
			
			token.process(operatorStack, output, this);
		}
		
		// Push everything from operator stack onto output queue.
		fillOutputQueue(operatorStack, output);
		
		// Create aggregator node out of all things left on stack.
		List<Node<T>> commands = new ArrayList<Node<T>>(output.size());
		for(int i = output.size()-1; i >= 0; i--) {
			commands.add(output.pop());
		}
		Collections.reverse(commands);
		
		return new Node<T>(commands);
	}

	/*
	 * Static so that we can access this from some process functions.
	 */
	public static<T> void fillOutputQueue(Stack<Token<T>> operatorStack,
			Stack<Node<T>> output) {
		while(!operatorStack.isEmpty()) {
			NodeToken<T> token = (NodeToken<T>) operatorStack.pop();
			output.add(token.makeNewInstance(output));
		}
	}
}
